
\subsubsection{Instancias de testeo}

Realizamos 3 experimentaciones diferentes y comparamos los resultados.

Todas las experimentaciones cumplen con que $100 <= n <= 10000$ y  las coordenadas de las ciudades son tales que $1 <= X <= 10000$, $1 <= Y <= 10000$.
El rango elegido para n se basa en que un n 'chico' reportaba tiempo de ejecución de 0 milisegundos(despreciable) y n mayor a 10000 tardaba mucho en terminar. Usar valores aleatorios entre 100 y 10000 nos da un espectro suficientemente amplio para visualizar el comportamiento del algoritmo. 

No encontramos mejores o peores casos para este algoritmo, entonces decidimos que cada experimentación se diferencie en el rango de valores elegido para k.

La primer experimentación fue de 200 instancias aleatorias. El rango elegido para k fue $50 <= k <= 5000$. 
Usamos esta primera experimentación para comparar con las demás. 

La segunda experimentación fue de 50 instancias aleatorias. Se tomo k igual al máximo valor de n, es decir k = 10000. 

La tercera experimentación fue de 50 instancias aleatorias. Se tomo k = 1.

Los valores de k tomados en la segunda y tercera experimentación, son los casos extremos en los que se puede colocar 1 central en cada ciudad y 1 central única para todas las ciudades respectivamente. Esperamos ver en los resultados que e algoritmo se comporte de la misma manera en las 3 experimentaciones, ya que el valor de k no influye en la complejidad.

\subsubsection{Resultados experimentales}

Los resultados obtenidos se pueden ver en el siguiente gráfico:\\

\includegraphics[scale=0.8]{ej2.png} \\

En el gráfico figuran las 3 experimentaciones juntas. El objetivo de esto es poder comparar fácilmente los resultados obtenidos de cada una(si la impresión es poco legible, por favor remitirse al png).

Las conclusiones que podemos sacar de los gráficos son:\\
- El algoritmo exhibe claramente una complejidad de $O(n^{2})$.\\
- Los distintos valores de k no influyen en el tiempo de ejecución del algoritmo, como se esperaba. Es más, ni siquiera se ve diferencia alguna entre los dos valores extremos de k para la segunda y tercer experimentación.